Medium
Related Topics: Array / Dynamic Programming
LeetCode Source

解題想法

暴力解的話，會使得時間複雜度是 O(m * n * n)

所以要透過額外的空間來找出上一層 points 的最大值

這裡是透過將上一層分為 left 跟 right 來找尋左邊或是右邊哪個地方會使得當前 cur 最大值

其中左邊 left，要先定義最左 left[0] = points[i][0]

接著透過 DP 儲存 left

left[j] = max(left[j-1]-1, prev[j])

而右邊 right，也需要定義最右 right[n-1] = points[i][n-1]

接著透過 DP 儲存 right

right[j] = max(right[j+1]-1, prev[j])

之後透過 cur 找尋哪一個值是最大值

cur[j] = max(left[j], right[j]) + points[i][j]

每次迴圈結束將 prev = cur

最後回傳最後一列當中的最大值

long long res = 0;

for (int i = 0; i < n; i++)
    res = max(res, prev[i]);

Complexity

Time Complexity: O(m * n)
Space Complexity: O(n)

Python

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        m, n = len(points), len(points[0])
        
        if m == 1:
            return max(points[0])
        if n == 1:
            return sum(sum(i) for i in points)

        def left(arr):
            l = [arr[0]] + [0] * (n-1)
            for i in range(1, n):
                l[i] = max(l[i-1]-1, arr[i])
            return l

        def right(arr):
            r = [0] * (n-1) + [arr[-1]]
            for i in range(n-2, -1, -1):
                r[i] = max(r[i+1]-1, arr[i])
            return r

        prev = points[0]

        for i in range(1, m):
            l, r, cur = left(prev), right(prev), [0] * n
            for j in range(n):
                cur[j] = points[i][j] + max(l[j], r[j])
            prev = cur
        return max(prev)

C++

class Solution {
public:
    long long maxPoints(vector<vector<int>>& points) {
        long long m = points.size(), n = points[0].size();

        vector<long long> prev(n);

        for (int i = 0; i < n; i++)
            prev[i] = points[0][i];

        for (int i = 1; i < m; i++) {
            vector<long long> l(n, 0), r(n, 0), cur(n, 0);
            l[0] = prev[0];
            r[n-1] = prev[n-1];
            for (int j = 1; j < n; j++) {
                l[j] = max(l[j-1]-1, prev[j]);
            }

            for (int j = n-2; j >= 0; j--) {
                r[j] = max(r[j+1]-1, prev[j]);
            }

            for (int j = 0; j < n; j++) {
                cur[j] = points[i][j] + max(r[j], l[j]);
            }
            prev = cur;
        }

        long long res = 0;

        for (int i = 0; i < n; i++) 
            res = max(res, prev[i]);
        return res;
    }
};